package leetcode.tree_problem;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 662. 二叉树最大宽度
 * https://leetcode-cn.com/problems/maximum-width-of-binary-tree/
 */
public class WidthOfBinaryTree {
    public int widthOfBinaryTree(TreeNode root) {
         if (root == null){
             return 0;
         }
         int maxWidth = 0;
        Deque<TreeNodeWithNum> deque = new LinkedList<>();
        //这步很有意思把头节点连编号一起放进队列
        deque.offer( new TreeNodeWithNum(root , 1));
        while (!deque.isEmpty()){
            int curWidth = 0;
            int curNumber = deque.size();
            //注意层元素个数就是队列的元素个数不用从0定义
            int numLeft = 0;
            int numRight = 0;
            for (int i = 0; i < curNumber; i++) {
                //移位出队只能一次但是判断要多次所以等以一个临时节点来存放出队保证判断的时候不会空指针
                //这个很巧妙刚好同时还能保证对内每个元素的遍历出队
                TreeNodeWithNum cur = deque.poll();
                if (i == 0){
                    numLeft = cur.num;
                }
                if (i == curNumber - 1){
                    numRight = cur.num;
                }
                //这就是题目的巧妙，他说与满二叉树结构相同，意味着每个编号的最右侧是前层的2倍 + 1
                if (cur.root.left != null){
                    deque.offer(new TreeNodeWithNum(cur.root.left , cur.num * 2)) ;
                }
                if (cur.root.right != null){
                    deque.offer(new TreeNodeWithNum(cur.root.right , cur.num * 2 + 1));
                }
                curWidth = numRight - numLeft + 1;
                //层宽这个也是满二叉树的性质就很巧妙

            }
            maxWidth = Math.max(maxWidth , curWidth);

        }
        return maxWidth;
    }
    private class TreeNodeWithNum {
        TreeNode root;
        int num;

        public TreeNodeWithNum(TreeNode root, int num) {
            this.root = root;
            this.num = num;
        }
    }
}
